﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace LinkUp
{
    /// <summary>
    /// 连连看的连线算法
    /// </summary>
    public class Path
    {
        public Path(int[,] mapData)
        {
            map = mapData;
        }

        /// <summary>
        /// 执行检查，判断是否相消
        /// </summary>
        /// <returns>true：可以消除；false：不能消除</returns>
        public bool Execute(int preIndex, int curIndex)
        {
            //int preClick = map.GetLength(0) + (preIndex - 1) / (map.GetLength(0) - 2) * 2 + preIndex;
            //int curClick = map.GetLength(0) + (curIndex - 1) / (map.GetLength(0) - 2) * 2 + curIndex;
            //this.startPos = new Point(preClick % map.GetLength(0), preClick / map.GetLength(0));
            //this.endPos = new Point(curClick % map.GetLength(0), curClick / map.GetLength(0));

            this.startPos = GetPointByIndex(preIndex);
            this.endPos = GetPointByIndex(curIndex);

            //检查目标位置是否一样
            if (this.startPos.X == this.endPos.X && this.startPos.Y == this.endPos.Y)
            {
                return false;
            }
            //检查为同一横坐标
            if (this.startPos.Y == this.endPos.Y)
            {
                this.EmptyPathRecord();
                if (this.CheckHorizontal(this.startPos, this.endPos, true))
                {
                    return true;
                }
            }
            //检查为同一纵坐标
            if (this.startPos.X == this.endPos.X)
            {
                this.EmptyPathRecord();
                if (this.CheckVertical(this.startPos, this.endPos, true))
                {
                    return true;
                }
            }
            //检查一个折点
            if (this.CheckOneCorner(this.startPos, this.endPos))
            {
                return true;
            }
            //检查两个折点
            if (this.CheckTwoCorner(this.startPos, this.endPos))
            {
                return true;
            }
            return false;
        }

        /// <summary>
        /// 根据index获取坐标
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public Point GetPointByIndex(int index)
        {
            int click = map.GetLength(0) + (index - 1) / (map.GetLength(0) - 2) * 2 + index;
            return new Point(click % map.GetLength(0), click / map.GetLength(0));
        }

        #region private functions

        private void EmptyPathRecord()
        {
            PathRecord.Clear();
            PathRecord.Add(this.startPos);
            PathRecord.Add(this.endPos);
        }

        private bool IsEmptyPoint(Point p)
        {
            return this.map[p.X, p.Y] == 0;
        }

        private bool CheckHorizontal(Point p1, Point p2)
        {
            return this.CheckHorizontal(p1, p2, false);
        }

        private bool CheckHorizontal(Point p1, Point p2, bool isAddPath)
        {
            //检查水平，x位移,y相同

            Point sp = p1.X < p2.X ? p1 : p2;
            Point ep = p2.X < p1.X ? p1 : p2;

            for (int x = sp.X + 1; x < ep.X; x++)
            {
                //允许记录
                if (isAddPath)
                {
                    this.PathRecord.Add(new Point(x, p1.Y));
                }
                //不可通过
                if (map[x, p1.Y] != 0)
                    return false;
            }
            return true;
        }

        private bool CheckVertical(Point p1, Point p2)
        {
            return CheckVertical(p1, p2, false);
        }

        private bool CheckVertical(Point p1, Point p2, bool isAddPath)
        {
            //检查垂直，y位移,x相同

            Point sp = p1.Y < p2.Y ? p1 : p2;
            Point ep = p2.Y < p1.Y ? p1 : p2;

            for (int y = sp.Y + 1; y < ep.Y; y++)
            {
                //允许记录
                if (isAddPath)
                {
                    this.PathRecord.Add(new Point(p1.X, y));
                }
                //不可通过
                if (map[p1.X, y] != 0)
                    return false;
            }
            return true;
        }

        private bool CheckOneCorner(Point p1, Point p2)
        {
            return CheckOneCorner(p1, p2, true, true);
        }

        private bool CheckOneCorner(Point p1, Point p2, bool isAddPath, bool isClear)
        {
            //计算夹角

            //取起始x
            Point CrossStart;
            Point CrossEnd;

            if (p1.X < p2.X)
            {
                CrossStart = p1;
                CrossEnd = p2;
            }
            else
            {
                CrossStart = p2;
                CrossEnd = p1;
            }

            //正向交叉点X
            Point CrossX;
            //反向交叉点Y
            Point CrossY;

            if (CrossStart.Y < CrossEnd.Y)
            {
                CrossX = new Point(
                    Math.Max(CrossStart.X, CrossEnd.X),
                    Math.Min(CrossStart.Y, CrossEnd.Y)
                    );
                CrossY = new Point(
                    Math.Min(CrossStart.X, CrossEnd.X),
                    Math.Max(CrossStart.Y, CrossEnd.Y)
                    );
            }
            else
            {
                CrossX = new Point(
                    Math.Min(CrossStart.X, CrossEnd.X),
                    Math.Min(CrossStart.Y, CrossEnd.Y)
                    );
                CrossY = new Point(
                    Math.Max(CrossStart.X, CrossEnd.X),
                    Math.Max(CrossStart.Y, CrossEnd.Y)
                    );
            }

            //检查交叉点是否为可通过
            if (!this.IsEmptyPoint(CrossX) && !this.IsEmptyPoint(CrossY))
                return false;

            //检查交叉点X
            if (this.IsEmptyPoint(CrossX))
            {
                //检查横位
                if (CrossStart.Y < CrossEnd.Y)
                {
                    //方向为~|
                    if (this.CheckHorizontal(CrossStart, CrossX) && this.CheckVertical(CrossX, CrossEnd))
                    {
                        //允许清空
                        if (isClear)
                        {
                            this.EmptyPathRecord();
                        }
                        //允许记录
                        if (isAddPath)
                        {
                            this.PathRecord.Add(CrossX); //记录当前交叉点
                        }
                        return (this.CheckHorizontal(CrossStart, CrossX, true) && this.CheckVertical(CrossX, CrossEnd, true));
                    }
                }
                else
                {
                    //方向为|~
                    if (this.CheckHorizontal(CrossX, CrossEnd) && this.CheckVertical(CrossX, CrossStart))
                    {
                        //允许清空
                        if (isClear)
                        {
                            this.EmptyPathRecord();
                        }
                        //允许记录
                        if (isAddPath)
                        {
                            this.PathRecord.Add(CrossX); //记录当前交叉点
                        }
                        return (this.CheckHorizontal(CrossX, CrossEnd, true) && this.CheckVertical(CrossX, CrossStart, true));
                    }
                }
            }
            //检查交叉点Y
            if (this.IsEmptyPoint(CrossY))
            {
                //检查竖位			
                if (CrossStart.Y < CrossEnd.Y)
                {
                    //方向为|_
                    if (this.CheckVertical(CrossStart, CrossY) && this.CheckHorizontal(CrossY, CrossEnd))
                    {
                        //允许清空
                        if (isClear)
                        {
                            this.EmptyPathRecord();
                        }
                        //允许记录
                        if (isAddPath)
                        {
                            this.PathRecord.Add(CrossY); //记录当前交叉点
                        }
                        return (this.CheckVertical(CrossStart, CrossY, true) && this.CheckHorizontal(CrossY, CrossEnd, true));
                    }
                }
                else
                {
                    //方向_|
                    if (this.CheckVertical(CrossEnd, CrossY) && this.CheckHorizontal(CrossY, CrossStart))
                    {
                        //允许清空
                        if (isClear)
                        {
                            this.EmptyPathRecord();
                        }
                        //允许记录
                        if (isAddPath)
                        {
                            this.PathRecord.Add(CrossY); //记录当前交叉点
                        }
                        return (this.CheckVertical(CrossEnd, CrossY, true) && this.CheckHorizontal(CrossY, CrossStart, true));
                    }
                }

            }
            return false; //全部不成立,留给2次折点检测
        }

        private bool CheckTwoCornerLeft(Point p1, Point p2, bool isAddPath)
        {
            //左
            //清空记录
            this.EmptyPathRecord();
            for (int x = p1.X - 1; x > -1; x--)
            {
                if (this.map[x, p1.Y] != 0)
                    return false;
                //允许记录
                if (isAddPath)
                {
                    this.PathRecord.Add(new Point(x, p1.Y));
                }

                //不允许清空
                if (this.CheckOneCorner(new Point(x, p1.Y), p2, false, false))
                {
                    return this.CheckOneCorner(new Point(x, p1.Y), p2, isAddPath, false);
                }
            }

            return false;
        }

        private bool CheckTwoCornerRight(Point p1, Point p2, bool isAddPath)
        {
            //右
            //清空记录
            this.EmptyPathRecord();
            for (int x = p1.X + 1; x < this.map.GetLength(0); x++)
            {
                if (this.map[x, p1.Y] != 0)
                    return false;
                //允许记录
                if (isAddPath)
                {
                    this.PathRecord.Add(new Point(x, p1.Y));
                }

                //不允许清空
                if (this.CheckOneCorner(new Point(x, p1.Y), p2, false, false))
                {
                    return this.CheckOneCorner(new Point(x, p1.Y), p2, isAddPath, false);
                }
            }

            return false;
        }

        private bool CheckTwoCornerUp(Point p1, Point p2, bool isAddPath)
        {
            //上
            //清空记录
            this.EmptyPathRecord();
            for (int y = p1.Y - 1; y > -1; y--)
            {
                if (this.map[p1.X, y] != 0)
                    return false;
                //允许记录
                if (isAddPath)
                {
                    this.PathRecord.Add(new Point(p1.X, y));
                }

                //不允许清空
                if (this.CheckOneCorner(new Point(p1.X, y), p2, false, false))
                {
                    return this.CheckOneCorner(new Point(p1.X, y), p2, isAddPath, false);
                }
            }
            return false;
        }

        private bool CheckTwoCornerDown(Point p1, Point p2, bool isAddPath)
        {
            //下
            //清空记录
            this.EmptyPathRecord();
            for (int y = p1.Y + 1; y < this.map.GetLength(1); y++)
            {
                if (this.map[p1.X, y] != 0)
                    return false;
                //允许记录
                if (isAddPath)
                {
                    this.PathRecord.Add(new Point(p1.X, y));
                }

                //不允许清空
                if (this.CheckOneCorner(new Point(p1.X, y), p2, false, false))
                {
                    return this.CheckOneCorner(new Point(p1.X, y), p2, isAddPath, false);
                }
            }

            return false;
        }

        private void CopyArrayListTo(ref List<Point> srcAl, ref List<Point> destAl)
        {
            if (srcAl == null || destAl == null)
                return;
            destAl.Clear();

            foreach (Point p in srcAl)
            {
                destAl.Add(p);
            }
        }

        private bool CheckTwoCorner(Point p1, Point p2)
        {
            //取起始x
            Point CrossStart;
            Point CrossEnd;

            if (p1.X < p2.X)
            {
                CrossStart = p1;
                CrossEnd = p2;
            }
            else
            {
                CrossStart = p2;
                CrossEnd = p1;
            }

            //寻找最短路径算法，查找四个方向，选出最短路径

            List<Point>[] backFindPath = new List<Point>[4];
            bool isFind = false;
            int nextPathList = 0;

            this.PathRecord.Clear();
            if (this.CheckTwoCornerUp(CrossStart, CrossEnd, true))
            {
                backFindPath[nextPathList] = new List<Point>();
                CopyArrayListTo(ref this.PathRecord, ref backFindPath[nextPathList]);
                isFind = true;
                nextPathList++;
            }

            this.PathRecord.Clear();
            if (this.CheckTwoCornerDown(CrossStart, CrossEnd, true))
            {
                backFindPath[nextPathList] = new List<Point>();
                CopyArrayListTo(ref this.PathRecord, ref backFindPath[nextPathList]);

                isFind = true;
                nextPathList++;
            }

            this.PathRecord.Clear();
            if (this.CheckTwoCornerLeft(CrossStart, CrossEnd, true))
            {
                backFindPath[nextPathList] = new List<Point>();
                CopyArrayListTo(ref this.PathRecord, ref backFindPath[nextPathList]);
                isFind = true;
                nextPathList++;
            }

            this.PathRecord.Clear();
            if (this.CheckTwoCornerRight(CrossStart, CrossEnd, true))
            {
                backFindPath[nextPathList] = new List<Point>();
                CopyArrayListTo(ref this.PathRecord, ref backFindPath[nextPathList]);
                isFind = true;
                nextPathList++;
            }
            //有结果返回
            if (isFind)
            {
                //检查起点最小数
                int minCount = 0;
                //记录位
                int index = 0;
                for (int i = 0; i < nextPathList; i++)
                {
                    if (backFindPath[i] != null && backFindPath[i].Count > 0)
                    {
                        if (minCount == 0)
                        {
                            minCount = backFindPath[i].Count;
                            index = i;
                        }
                        else if (backFindPath[i].Count < minCount)
                        {
                            minCount = backFindPath[i].Count;
                            index = i;
                        }
                    }
                }
                //回复属性数据
                this.PathRecord.Clear();
                CopyArrayListTo(ref backFindPath[index], ref this.PathRecord);
                return true;
            }
            //没有结果
            else
                return false; ;
        }
        #endregion

        #region field and property
        private Point startPos; //起点
        /// <summary>
        /// 起点坐标
        /// </summary>
        public Point StartPosition
        {
            get { return this.startPos; }
            set { this.startPos = value; }
        }
        private Point endPos; //终点
        /// <summary>
        /// 终点坐标
        /// </summary>
        public Point EndPosition
        {
            get { return this.endPos; }
            set { this.endPos = value; }
        }
        private List<Point> PathRecord = new List<Point>();
        /// <summary>
        /// 获取路径表
        /// </summary>
        public List<Point> PathPointList
        {
            get { return this.PathRecord; }
        }
        private int[,] map = null; //地图
        /// <summary>
        /// 地图数据
        /// </summary>
        public int[,] MapData
        {
            get { return this.map; }
            set { this.map = value; }
        }
        #endregion
    }
}
